题解 CF1167B@洛谷 | 1167B@Codeforces 【Lost Numbers】

我们有一个由 4,8,15,16,23,424,8,15,16,23,42 组成的排列,只能询问四次两个位置上的数的乘积。

下面是一些可能会考虑到的错误的策略(也是我做题时的思路),在这里放出体现我们的思考过程:

策略 1:每次询问两个相同的下标 ii 和它本身。

这种策略是最容易想到的,但是这样的话只能询问出 44 个位置的值,剩下两个位置就没办法了。考虑其它策略。

策略 2:询问 1111 的乘积,得到第一个数,此后三次询问 (1,2)(2,3)(3,4)(1,2)(2,3)(3,4)

和策略 1 有着同样的问题。


正确策略

通过上面的思考,我们得到了一个结论:只有 44 个位置是显然不行的,考虑添加第五个位置。

我们可以询问 (1,2)(2,3)(3,4)(4,5)(1,2)(2,3)(3,4)(4,5),这样就能方便的获得和五个位置相关的信息。

具体解法

在按照上面的策略询问完前五个数后得到了四个答案(代码中记做 mutiplemutiple),我们枚举所有 6!=7206!=720 种可能的排列情况,对于每个排列,循环一遍判断是否符合询问得到的答案即可。

但是这样还不够,我们还要知道满足四个答案的排列是唯一的

唯一性证明

自己口胡的,可能不太严谨,但是自认为比较好理解,可以手玩几个理解一下。

因为上面数列任意两个数的乘积都不同,我们想到,满足 ai×aj=ka_i\times a_j=k 的只有两种可能,即 iijj 交换。而上面就相当于固定了前五个数,因为数列中的六个数给定,可以通过排除来获得第六个数的信息。

唯一性得证,策略正确。


代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int a[7] = {-1, 4, 8, 15, 16, 23, 42}, multiple[5];

int main() {
	for(int i=1;i<=4;i++) {
		printf("? %d %d\n", i, i+1);
		fflush(stdout);
		scanf("%d", &multiple[i]);
	}
	do {
		bool _ = true;
		for(int i=1;i<=4;i++) {
			if(a[i] * a[i+1] != multiple[i]) {
				_ = false;
				break;
			}
		}
		if(_) {
			printf("! ");
			for(int i=1;i<=6;i++) printf("%d ", a[i]);
			puts("");
			break;
		}
	}while(next_permutation(a+1, a+7));
	return 0;
}